package com.fzkj.algorithm;

import java.util.ArrayList;
import java.util.List;

public class SortedListToBST {
    /**
     *
     给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

     本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

     示例:

     给定的有序链表： [-10, -3, 0, 5, 9],

     一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

         0
        / \
      -3   9
      /   /
     -10  5
     */


    // 看了网上的解决方案，有快慢指针的，还有其他方法的。
    // 总之就是先找到链表的中间元素作为二叉树的跟节点，然后左边的作为左子树，右边的作为右子树。
    // 总的来说还是递归。。找到左子树之后用相同的方法找到跟节点。在找左子树、右子树。

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode sortedListToBST(ListNode head) {
        // 先将链表转换为列表
        if (head == null ) return null;
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        return helper(list, 0, list.size() - 1);
    }

    public TreeNode helper(List<Integer> list, int left, int right){
        //
        if (null == list || left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = helper(list, left, mid - 1);
        root.right = helper(list,mid + 1, right);
        return root;
    }



}
